/*
 * @lc app=leetcode.cn id=675 lang=typescript
 *
 * [675] 为高尔夫比赛砍树
 */

// @lc code=start
interface NextData {
  x: number;
  y: number;
  steps: number;
}

function cutOffTree(forest: number[][]): number {
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];

  const m = forest.length;
  const n = forest[0].length;
  // 广度优先搜索，每次搜索一个树的访问路径
  const bfs = (sx: number, sy: number, tx: number, ty: number): number => {
    if (sx === tx && sy === ty) return 0;
    const visited: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0));
    const queue: NextData[] = [];
    // 初始化起点
    queue.push({ x: sx, y: sy, steps: 0 });
    visited[sx][sy] = 1;
    while (queue.length) {
      const curr = queue.shift()!;
      if (curr.x === tx && curr.y === ty) return curr.steps;
      for (const [dx, dy] of dirs) {
        const nx = curr.x + dx;
        const ny = curr.y + dy;
        if (nx < 0 || nx >= m) continue;
        if (ny < 0 || ny >= n) continue;
        if (forest[nx][ny] === 0) continue;
        if (visited[nx][ny]) continue;
        visited[nx][ny] = 1;
        queue.push({ x: nx, y: ny, steps: curr.steps + 1 });
      }
    }
    return -1;
  };

  // 将所有的树的位置放入一个数组中，并且按照树的高度从小到大排序
  const trees = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (forest[i][j] > 1) {
        trees.push([i, j]);
      }
    }
  }
  trees.sort((a: number[], b: number[]) => forest[a[0]][a[1]] - forest[b[0]][b[1]]);

  // 对每一个树进行广度优先搜索，找到路径
  let ans = 0;
  let sx = 0;
  let sy = 0;
  for (let i = 0; i < trees.length; i++) {
    let steps = bfs(sx, sy, trees[i][0], trees[i][1]);
    if (steps === -1) return -1;
    ans += steps;
    sx = trees[i][0];
    sy = trees[i][1];
  }
  return ans;
}
// @lc code=end
